P4054 计数问题

题目描述

一个 $n\times m$ 的方格，初始时每个格子有一个整数权值。接下来每次有 2 种操作：

• 改变一个格子的权值；

• 求一个子矩阵中某种特定权值出现的个数。

输入格式

第一行有两个数 $n,m$。

接下来 $n$ 行，每行 $m$ 个数，第 $i+1$ 行第 $j$ 个数表示格子 $(i,j)$ 的初始权值。

接下来输入一个整数 $Q$。

之后 $Q$ 行，每行描述一个操作。

操作 1：输入一行四个整数 $1xyc$，表示将格子 $(x,y)$ 的权值改成 $c$。

操作 2：输入一行六个整数 $2x_1{x}_2{y}_1{y}_{2}c$。表示询问所有满足格子颜色为 $c$，且满足 $x_1\le x\le x_2,y_1\le y\le y_2$ 的格子个数。

输出格式

对于每个操作 2，按照在输入中出现的顺序，依次输出一行一个整数表示所求得的个数。

满足：$1\le n,m\le 300$，$1\le Q\le 2\times {10}^5$。

对于操作 1，保证：$1\le x\le n$，$1\le y\le m$，$1\le c\le 100$；

对于操作 2，保证：$1\le x_1\le x_2\le n$，$1\le y_1\le y_2\le m$，$1\le c\le 100$。

Solution

二维树状数组

#define lowbit(x) x&(-x)
int a[310][310], n, m, c[310][310][110];
void add(int x, int y, int k, int color) {
    for (int i = x;i <= n;i += lowbit(i)) {
        for (int j = y;j <= m;j += lowbit(j)) {
            c[i][j][color] += k;
        }
    }
}
int query(int x, int y, int color) {
    int ans = 0;
    for (int i = x;i;i -= lowbit(i)) {
        for (int j = y;j;j -= lowbit(j)) {
            ans += c[i][j][color];
        }
    }
    return ans;
}
void solve() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            int x;cin >> x;
            a[i][j] = x;
            add(i, j, 1, x);
        }
    }
    int q;cin >> q;
    while (q--) {
        int op;cin >> op;
        if (op == 1) {
            int x, y, c;cin >> x >> y >> c;
            add(x, y, -1, a[x][y]);
            a[x][y] = c;
            add(x, y, 1, c);
        } else {
            int x1, x2, y1, y2, c;cin >> x1 >> x2 >> y1 >> y2 >> c;
            cout << 
            query(x2, y2, c) - query(x1 - 1, y2, c) - query(x2, y1 - 1, c) + query(x1 - 1, y1 - 1, c) 
            << '\n';
        }
    }
}